#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <map>
#include <climits>

using namespace std;

/*
1. 求全排列数

*/
int n,m,k,x;
int ans;
void printv(vector<int> &v){
    for(auto x : v){
        cout << x << " ";
    }cout <<endl;
}
int can(vector<int> &t,vector<int> &v){
    int64_t tmp=0;
    for(int i=0;i<m;i++){
        tmp=tmp*10+v[t[i]-1];
    }
    if(tmp%x!=k){
        return false;
    }
    for(int i=0;i<m-1;i++){
        if((v[t[i+1]-1]+v[t[i]-1])%2==0){
            return false;
        }
    }
    return true;
}

//用它来搜索所有的组合
void dfs(int n,int k,int cur,vector<int> &t,vector<int> &v){
    if(t.size()+(n-cur+1)<k){
        return;
    }
    if(t.size()==k){
       printv(t);
        if(can(t,v)){
            ans++;
            //printv(t);
        }
        return;
    }
    t.push_back(cur);
    dfs(n,k,cur+1,t,v);
    t.pop_back();
    dfs(n,k,cur+1,t,v);
}




int main(){
    cin >> n >> m >> k>> x;
    vector<int> v(n,0);
    for(int i=0;i<n;i++){
        cin >> v[i];
    }
    //cout << solve(v)<<endl;
    vector<int> t;
    dfs(n,m,1,t,v);
    cout << ans <<endl;
    return 0;
}